/*  GStruct: data structure helpers for Java
 *  Copyright (C) 2011 Giulio Franco
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package gstruct.sequential;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

/**
 * List implementation based on linked list that actually
 * exposes its nodes, to allow more efficient operation than
 * it's allowed by Java {@link LinkedList}s.
 * @author Giulio Franco <giulio_franco@msn.com>
 *
 * @param <E>	Type of contained items.
 */
public class DecentLinkedList<E> implements List<E> {
	
	/**
	 * Node contained in the list
	 * @author Giulio Franco <giulio_franco@msn.com>
	 *
	 * @param <E>	Type of the contained item
	 */
	public static class LinkedListNode<E> {
		private DecentLinkedList<E> list;
		private E item;
		private LinkedListNode<E> prev;
		private LinkedListNode<E> next;
		
		private LinkedListNode(DecentLinkedList<E> list, E item, LinkedListNode<E> prev, LinkedListNode<E> next) {
			this.list = list;
			this.item = item;
			this.prev = prev;
			this.next = next;
		}
		
		/**
		 * Gets the previous item in the list
		 * @return	previous item in the list,
		 * 			or null if the current item is the first one.
		 */
		public LinkedListNode<E> getPrevious() { return (prev == list.head) ? null : prev; }
		
		
		/**
		 * Gets the next item in the list
		 * @return	next item in the list,
		 * 			or null if the current item is the last one.
		 */
		public LinkedListNode<E> getNext() { return (next == list.tail) ? null : next; }
		
		/**
		 * Gets the item contained in this node
		 * @return content of this node
		 */
		public E getItem() { return item; }
		
		/**
		 * Gets the list owning this node.
		 * @return list containing this node, or null if none.
		 */
		public DecentLinkedList<E> getList() { return list; }
	}

	
	private final DecentLinkedList<E> baseList;
	private final LinkedListNode<E> head;
	private final LinkedListNode<E> tail;
	private int size;
	
	/**
	 * Creates a new list
	 */
	public DecentLinkedList() {
		baseList = this;
		head = new LinkedListNode<E>(this, null, null, null);
		tail = new LinkedListNode<E>(this, null, head, null);
		head.next = tail;
		size = 0;
	}
	
	/**
	 * Creates a sublist of an existing list
	 * @param base	Base list
	 * @param head	Head node
	 * @param tail	Tail node
	 * @param size	Length of the sublist
	 */
	private DecentLinkedList(DecentLinkedList<E> base, LinkedListNode<E> head, LinkedListNode<E> tail, int size) {
		this.baseList = base;
		this.head = head;
		this.tail = tail;
		this.size = size;
	}
	
	protected final LinkedListNode<E> checkNode(LinkedListNode<E> node)
			throws IllegalArgumentException {
		if (node.list != this.baseList) {
			throw new IllegalArgumentException("The node does not belong to this list");
		} else {
			return node;
		}
	}
	
	/**
	 * Adds an element at the end of the list
	 * @param arg0	Element to insert
	 * @return true
	 */
	@Override
	public boolean add(E arg0) {
		addLast(arg0);
		return true;
	}
	
	/**
	 * Adds an element at the beginning of the list
	 * @param arg0	Element to add
	 */
	public void addFirst(E arg0) {
		addAfter(head, arg0);
	}
	
	/**
	 * Adds an element at the end of the list
	 * @param arg0	Element to add
	 */
	public void addLast(E arg0) {
		addBefore(tail, arg0);
	}
	
	/**
	 * Gets the i-th node in the list
	 * @param index index
	 * @return index-th node in the list
	 */
	public LinkedListNode<E> getNode(int index) {
		checkIndex(index);
		
		LinkedListNode<E> n;
		int i = 0;
		for (n = head.next; i != index && n != tail; n = n.next) {
			i += 1;
		}
		
		return n;
	}
	
	/**
	 * Adds an element at the i-th position in the list
	 * @param arg0	Position arg1 will occupy
	 * @param arg1	Element to add
	 */
	@Override
	public void add(int arg0, E arg1) {
		if (arg0 == size) {
			add(arg1);
		} else {
			addBefore(getNode(arg0), arg1);
		}
	}

	/**
	 * Adds multiple elements at the end of the list
	 * @param arg0	Collection of elements to add
	 * @return true, if arg0 is not empty
	 */
	@Override
	public boolean addAll(Collection<? extends E> arg0) {
		return addAllBefore(tail, arg0);
	}
	
	/**
	 * Adds multiple elements, starting from a given index
	 * @param arg0	Position the first element of arg1 will occupy
	 * @param arg1	Collection of elements to add
	 * @return true, if arg1 is not empty 
	 */
	@Override
	public boolean addAll(int arg0, Collection<? extends E> arg1) {
		if (arg0 == size) {
			return addAll(arg1);
		} else {
			return addAllBefore(getNode(arg0), arg1);
		}
	}
	
	/**
	 * Adds multiple elements before a given node
	 * @param n		Node that will follow the last element of arg1
	 * @param arg1	Collection of elements to add
	 * @return		true, if arg1 is not empty
	 */
	public boolean addAllBefore(LinkedListNode<E> n, Collection<? extends E> arg1) {
		boolean modified = false;
		for (E e : arg1) {
			addBefore(n, e);
			modified = true;
		}
		return modified;
	}
	
	/**
	 * Adds multiple elements after a given node
	 * @param n		Node that will precede the first element of arg1
	 * @param arg1	Collection of elements to add
	 * @return		true, if arg1 is not empty
	 */
	public boolean addAllAfter(LinkedListNode<E> n, Collection<? extends E> arg1) {
		return addAllBefore(checkNode(n).next, arg1);
	}

	/**
	 * Removes all the elements contained in the list
	 */
	@Override
	public void clear() {
		head.next.prev = null;
		if (tail.prev != null) {
			tail.prev.next = null;
		}
		head.next = tail;
		tail.prev = head;
		this.size = 0;
	}
	
	/**
	 * Checks if an item is contained in the list
	 * @param o	Item to look for
	 * @return true iff a node n exists in the list so that
	 * 			<pre>n.getItem().equals(o)</pre>
	 */
	@Override
	public boolean contains(Object o) {
		for (E item : this) {
			if (o==null ? item == null : o.equals(item)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Checks if the list contains all the items in a given collection
	 * @param arg0	Collection of items to search
	 * @return true iff <pre>this.contains(o)</pre> for all elements in arg0.
	 */
	@Override
	public boolean containsAll(Collection<?> arg0) {
		for (Object o : arg0) {
			if (!contains(o)) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Gets the i-th element in the list
	 * @param arg0 Index of the element to retrieve
	 * @return Element at the i-th position
	 */
	@Override
	public E get(int arg0) {
		return getNode(arg0).item;
	}

	/**
	 * Gets the position of an item
	 * @param o	Item to look for
	 * @return Smallest index i so that <pre>get(i).equals(o)</pre>
	 * or -1 if no such index exists.
	 */
	@Override
	public int indexOf(Object o) {
		int i = 0;
		for (E item : this) {
			if (o==null ? item == null : o.equals(item)) {
				return i;
			}
			++i;
		}
		return -1;
	}
	
	/**
	 * Gets the node associated to item o
	 * @param o	Item to look for
	 * @return	First node n so that <pre>n.getItem().equals(o)</pre>
	 * 			or null if no such node exists
	 */
	public LinkedListNode<E> nodeOf(Object o) {
		for (LinkedListNode<E> n = head.next; n != tail; n = n.next) {
			if (o==null ? n.item == null : o.equals(n.item)) {
				return n;
			}
		}
		return null;
	}
	
	/**
	 * Gets the last node associated to item o
	 * @param o	Item to look for
	 * @return	Last node n so that <pre>n.getItem().equals(o)</pre>
	 * 			or null if no such node exists
	 */
	public LinkedListNode<E> lastNodeOf(Object o) {
		for (LinkedListNode<E> n = tail.prev; n != head; n = n.prev) {
			if (o==null ? n.item == null : o.equals(n.item)) {
				return n;
			}
		}
		return null;
	}

	/**
	 * Checks if the list is empty
	 * @return true iff the list is empty
	 */
	@Override
	public boolean isEmpty() {
		return head.next == tail;
	}
	
	@Override
	public Iterator<E> iterator() {
		return new DecentLinkedListIterator<>(this);
	}

	/**
	 * Gets the position of an item
	 * @param o	Item to look for
	 * @return Greatest index i so that <pre>get(i).equals(o)</pre>
	 * or -1 if no such index exists.
	 */
	@Override
	public int lastIndexOf(Object o) {
		int i = 0;
		int res = -1;
		for (E item : this) {
			if (o==null ? item == null : o.equals(item)) {
				res = i;
			}
			++i;
		}
		return res;
	}

	@Override
	public ListIterator<E> listIterator() {
		return new DecentLinkedListIterator<>(this);
	}

	@Override
	public ListIterator<E> listIterator(int arg0) {
		checkIndex(arg0);
		
		ListIterator<E> res = listIterator();
		while (arg0-- > 0) {
			res.next();
		}
		return res;
	}

	private int checkIndex(int index) {
		if (index < 0 || index >= size()) {
			throw new IndexOutOfBoundsException(index + "/" + size());
		}
		return index;
	}

	@Override
	public boolean remove(Object arg0) {
		LinkedListNode<E> n = nodeOf(arg0);
		if (n == null) {
			return false;
		} else {
			remove(n);
			return true;
		}
	}

	/**
	 * Removes a node (along with the item it contains)
	 * from the list
	 * @param n		Node to remove. Must be owned by this list
	 */
	public void remove(LinkedListNode<E> n) {
		checkNode(n);
		n.list = null;
		n.prev.next = n.next;
		n.next.prev = n.prev;
		n.prev = null;
		n.next = null;
		size -= 1;
	}
	
	@Override
	public E remove(int arg0) {
		LinkedListNode<E> n = getNode(arg0);
		remove(n);
		return n.item;
	}

	@Override
	public boolean removeAll(Collection<?> arg0) {
		boolean modified = false;
		for (Object o : arg0) {
			modified |= remove(o);
		}
		return modified;
	}

	@Override
	public boolean retainAll(Collection<?> arg0) {
		boolean modified = false;
		for (LinkedListNode<E> n = head.next; n != tail; n = n.next) {
			if (!arg0.contains(n.item)) {
				modified = true;
				LinkedListNode<E> toRemove = n;
				n = n.prev;
				remove(toRemove);
			}
		}
		return modified;
	}

	@Override
	public E set(int arg0, E arg1) {
		LinkedListNode<E> n = getNode(arg0);
		E res = n.item;
		n =n.next;
		remove(n.prev);
		addBefore(n, arg1);
		return res;
	}

	/**
	 * Adds an element before a given node
	 * @param n		Node that will follow the newly added one
	 * @param arg1	Element to add
	 */
	public void addBefore(LinkedListNode<E> n, E arg1) {
		checkNode(n);
		LinkedListNode<E> nn = new LinkedListNode<E>(baseList, arg1, n.prev, n);
		n.prev = nn;
		nn.prev.next = nn;
		size += 1;
	}
	
	/**
	 * Adds an element after a given node
	 * @param n		Node that will precede the newly added one
	 * @param arg0	Element to add
	 */
	public void addAfter(LinkedListNode<E> n, E arg0) {
		addBefore(n.next, arg0);
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public DecentLinkedList<E> subList(int arg0, int arg1) {
		LinkedListNode<E> newHead = getNode(arg0);
		LinkedListNode<E> newTail = getNode(arg1).next;
		return new DecentLinkedList<>(baseList, newHead, newTail, arg1 - arg0);
	}

	@Override
	public Object[] toArray() {
		Object[] res = new Object[size];
		int i = 0;
		for (LinkedListNode<E> n = head.next; n != tail; n = n.next) {
			res[i++] = n.item;
		}
		return res;
	}

	@Override
	public <T> T[] toArray(T[] arg0) {
		if (arg0.length < size) {
			arg0 = Arrays.copyOf(arg0, size);
		}
		
		int i = 0;
		for (LinkedListNode<E> n = head.next; n != tail; n = n.next) {
			arg0[i++] = (T)n.item;
		}
		return arg0;
	}

	/**
	 * Gets the first node in the list
	 * @return	First node in the list
	 */
	public LinkedListNode<E> getFirstNode() {
		return head.getNext();
	}
	
	/**
	 * Gets the last node in the list
	 * @return	Last node in the list
	 */
	public LinkedListNode<E> getLastNode() {
		return tail.getPrevious();
	}

	/**
	 * Gets the first element in the list
	 * @return 	First element in the list
	 */
	public E getFirst() {
		LinkedListNode<E> n = getFirstNode();
		return (n == null) ? null : n.item;
	}
	
	/**
	 * Gets the last element in the list
	 * @return	Last element in the list
	 */
	public E getLast() {
		LinkedListNode<E> n = getLastNode();
		return (n == null) ? null : n.item;
	}
	
	/**
	 * Returns an iterable collection of the nodes contained in this list
	 * @return	Iterable collection of nodes
	 */
	public Iterable<LinkedListNode<E>> getNodes() {
		return new LinkedListNodeList<>(this);
	}

	@Override
	public String toString() {
		StringBuilder bdr = new StringBuilder(getClass().getSimpleName());
		bdr.append("[");
		for (E e : this) {
			bdr.append(e).append(", ");
		}
		bdr.setLength(bdr.length() - 2);
		bdr.append("]");
		return bdr.toString();
	}
}
